package com.arron.algorithm.leetcodetop100.前缀和;

import java.util.Random;

public class 按权重随机匹配 {


    int[] prefixSum;

    public void Solution(int[] w) {

        prefixSum = new int[w.length+1];

        for (int i = 1; i < prefixSum.length; i++) {
            prefixSum[i] =  prefixSum[i-1] +w[i-1];
        }


    }

    public int pickIndex() {

        int random =1+  (int) new Random().nextInt(prefixSum[prefixSum.length-1]);

        int left = 0;
        int right = prefixSum.length-1;

        int resIndex = 0;
        while (left <= right){

            int mid = left+ (right-left)/2;

            if (prefixSum[mid] > random){
                right = mid -1;
            }else if (prefixSum[mid] < random){
                left = mid +1;
            }else {
                resIndex = mid;
                break;
            }
        }

        return resIndex ==0?left-1:resIndex-1;
    }


    public static void main(String[] args) {
        按权重随机匹配 rand = new 按权重随机匹配();
        int[] w={3,14,1,7};
        rand.Solution(w);



        while (true){
            System.out.println(rand.pickIndex());
//            int random = new Random().nextInt(5);
//            System.out.println(random);
        }

    }




}
